#pragma once

#include "Graph.h"
#include "GraphAlgorithms.h"
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#include <set>

namespace{

	class StronglyComponentsFindClass{
		int timerCount_;
		std::vector<int> lowestTimes_;
		std::stack<int> vertexStack_;
		std::vector<int> componentsResult_;
		std::vector<int> timeIn_;
		int currentComponentNum_ = 0;
	public:
		explicit StronglyComponentsFindClass(int numVertex){
			timerCount_ = 0;
			lowestTimes_.resize(numVertex);
			timeIn_.resize(numVertex);
			componentsResult_.assign(numVertex, -1);
		}

		const void beforeStep(int startVertex) const{
		}

		void processEdge(int toVertex, int fromVertex, colors color){
			if (color == WHITE){
				timerCount_++;
				lowestTimes_[toVertex] = timerCount_;
				timeIn_[toVertex] = timerCount_;
				vertexStack_.push(toVertex);
			}
			else if (color == GREY){
				lowestTimes_[fromVertex] = std::min<int>(lowestTimes_[fromVertex], lowestTimes_[toVertex]);
			}
			else if (color == BLACK){
				if (componentsResult_[toVertex] == -1)
					lowestTimes_[fromVertex] = std::min<int>(lowestTimes_[fromVertex], lowestTimes_[toVertex]);
			}
		}


		void afterCurrentStep(int vertex, int parent){
			if (parent != -1){
				lowestTimes_[parent] = std::min<int>(lowestTimes_[parent], lowestTimes_[vertex]);
			}
			if (lowestTimes_[vertex] == timeIn_[vertex]){

				while (true){
					if (vertexStack_.empty()){
						throw std::length_error("Stack for strongly components is empty");
					}
					int addedVertex = vertexStack_.top();
					vertexStack_.pop();
					componentsResult_[addedVertex] = currentComponentNum_;
					if (addedVertex == vertex)
						break;
				}
				++currentComponentNum_;
				timerCount_++;
			}

		}


		const void afterDFS() const{}

		const std::vector<int> getComponentsList() const{
			return componentsResult_;
		}
	};



	std::unique_ptr<Graph> buildingCondenstaionGraph(Graph &G, 
		std::vector<int>& componentsList){
		StronglyComponentsFindClass connectedClass(G.getVertexNum());
		DFS(G, &connectedClass);
		componentsList = connectedClass.getComponentsList();
		std::set<Edge> edgesSet;
		int maxNumberOfComponent = 0;
		for (auto currentVertex : componentsList){
			maxNumberOfComponent = std::max<int>(maxNumberOfComponent, currentVertex);
		}
		for (int currentVertex = 0; currentVertex < G.getVertexNum(); ++currentVertex){
			std::vector<int> currentAdjacentList = G.getAdjacentList(currentVertex);
			for (auto connectedVertex : currentAdjacentList){
				edgesSet.insert({componentsList[currentVertex], componentsList[connectedVertex] });
			}
		}
		std::vector<Edge> condenstatedEdgesList;
		for (auto currentEdge : edgesSet){
			if (currentEdge.fromVertex != currentEdge.toVertex)
				condenstatedEdgesList.push_back(currentEdge);
		}
		return  readGraph(maxNumberOfComponent + 1, condenstatedEdgesList);
	}
}
